package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 2/5/21 9:45 AM
 *
 * https://leetcode-cn.com/problems/get-equal-substrings-within-budget/
 *
 *  子字串要连续
 */
public class _1208_尽可能使字符串相等 {

    public int equalSubstring(String s, String t, int maxCost) {

        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        int len = sChars.length;
        int[] sums = new int[len + 1];

        int index;
        for (int i = 1; i < sums.length; i++) {

            index = i - 1;
            sums[i] = sums[index] + Math.abs(sChars[index] - tChars[index]);
        }

        int maxLen = 0;
        for (int i = 1; i < sums.length; ++i) {

            index = find(sums,i,sums[i] - maxCost);
            maxLen = Math.max(i - index ,maxLen);
        }

        return maxLen;
    }

    private static int find(int[] sums, int end, int target) {

        // 最左边第一个满足:sums[index] >= target 的index
        int start = 0;

        while (start < end) {

            int mid = ((end -start) >> 1) + start;

            if (target <= sums[mid]) {

                end = mid;
            }else  if (target > sums[mid]) {

                start = mid + 1;
            }
         }

        return start;
    }

    public int equalSubstring01(String s, String t, int maxCost) {

        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        int len = sChars.length;
        int[] distances = new int[len];

        for (int i = 0; i < len; i++) {

            distances[i] = Math.abs(sChars[i] - tChars[i]);
        }

        int preIndex = 0;
        int sum = 0;
        for (int i = 0; i < len; i++) {

            sum += distances[i];

            if (sum > maxCost) {

                sum -= distances[preIndex];
                preIndex++;
            }
        }

        return len - preIndex;
    }

}
